/*                  A
 *              B         C
 *                D     E      
 *              F     G   H
 *
*/

#include <stdio.h>
#include <stdlib.h>


typedef struct TreeNode {
    char data;
    struct TreeNode *lchild;
    struct TreeNode *rchild;
} TreeNode;

void creatTree(TreeNode **T, char *data, int *index)
{
    char ch;
    ch = data[*index];
    (*index)++;
    if (ch == '#') {//递归结束
        *T = NULL;
    } else {
        *T = (TreeNode *)malloc(sizeof(TreeNode));
        (*T)->data = ch;
        //递归左右
        creatTree(&((*T)->lchild), data, index);
        creatTree(&((*T)->rchild), data, index);
    }
}

void preOrder(TreeNode *T)
{
    if (!T) return ;
    printf("%c ", T->data);
    preOrder(T->lchild);
    preOrder(T->rchild);
}

void inOrder (TreeNode *T) 
{
    if (!T) return ;
    inOrder(T->lchild);
    printf("%c ", T->data);
    inOrder(T->rchild);
}

void posOrder (TreeNode *T) 
{
    if (!T) return ;
    posOrder(T->lchild);
    posOrder(T->rchild);
    printf("%c ", T->data);
}

int main(void) 
{ 
    int index = 0;
    
    TreeNode *T;
    creatTree(&T, "AB#DF###CEG##H###", &index); //p141

    preOrder(T);
    printf("\n");
    inOrder(T);
    printf("\n");
    posOrder(T);

    return 0;
}

//由于scanf()需要多打个#
/*
void _creatTree(TreeNode **T) 
{
    char data;
    scanf("%c\n", &data);
    if (data == '#') {//递归结束
        *T = NULL;
    } else {
        *T = (TreeNode *)malloc(sizeof(TreeNode));
        (*T)->data = data;
        //递归左右
        _creatTree(&((*T)->lchild));
        _creatTree(&((*T)->rchild));
    }
}
*/

/*
void *creatTree(TreeNode **T) 
{
    char data;
    data = scanf("%c\n", &data);
    if (data == '#') {//递归结束
        *T = NULL;
    } else {
        *T = (TreeNode *)malloc(sizeof(TreeNode));
        (*T)->data = data;
        //递归左右
        creatTree(&((*T)->lchild));
        creatTree(&((*T)->rchild));
    }
}
*/